# always TLE

import sys

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        # """
        # :type beginWord: str
        # :type endWord: str
        # :type wordList: Set[str]
        # :rtype: int
        # """
        # wordList = list(wordList)
        # wordList.extend([beginWord, endWord])

        # dist = [sys.maxsize for _ in range(len(wordList))]
        # inSet = [False for _ in range(len(wordList))]
        # dist[-2] = 0

        # for _ in range(len(wordList)):
        #     minDist = sys.maxsize
        #     minIndex = -1
        #     for i in range(len(wordList)):
        #         if not inSet[i] and dist[i]<minDist:
        #             minDist=dist[i]
        #             minIndex=i
        #     if minIndex==-1:
        #         break
        #     inSet[minIndex]=True
        #     dist[minIndex]=minDist
        #     for i in range(len(wordList)):
        #         dif=0
        #         for c1, c2 in zip(wordList[minIndex], wordList[i]):
        #             if c1!=c2:
        #                 dif+=1
        #         if dif==1:
        #             alt = dist[minIndex]+1
        #             if alt<dist[i]:
        #                 dist[i]=alt
        
        # return dist[-1]+1 if dist[-1]!=sys.maxsize else 0
        #BSF
        wordList.add(endWord)
        wordList.remove(beginWord)
        wordList = list(wordList)
        def bsf(word, avaliable):
            if word==endWord:
                return 1
            minDep = sys.maxsize
            for i in range(len(wordList)):
                w=wordList[i]
                a=avaliable[i]
                if a and sum(map(lambda pair: 1 if pair[0]!=pair[1] else 0, zip(word, w)))==1:
                    avaliable[i]=False
                    dep = bsf(w, avaliable)
                    minDep = min(minDep, dep)
                    avaliable[i]=True
            return minDep+1
        avaliable = [True for _ in range(len(wordList))]
        result = bsf(beginWord, avaliable)
        return 0 if result>=sys.maxsize else result

print(Solution().ladderLength("red","tax",["ted","tex","red","tax","tad","den","rex","pee"]))